package com.kabuda.zhugehot200;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author kabuda
 * @date 2025-03-18 21:23
 * @description
 */
public class t547_省份数量 {
    public static void main(String[] args) {
        int[][] isConnected = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
        System.out.println(new t547_省份数量().findCircleNum(isConnected));
        System.out.println(new t547_省份数量().bfs(isConnected));
        System.out.println(new t547_省份数量().mergeFind(isConnected));
    }

    public int findCircleNum(int[][] isConnected) {
        //城市数量
        int length = isConnected.length;
        //省份数量
        int provinces = 0;
        //城市是否被访问过
        boolean isVisited[] = new boolean[length];

        //遍历各个城市
        for (int i = 0; i < length; i++) {
            //没有被访问过才进去
            if (!isVisited[i]) {
                //进来了就算一个省份
                provinces++;
                //然后把相邻的城市全部都标记为访问过
                dfs(isConnected, isVisited, length, i);
            }
        }

        return provinces;
    }

    public void dfs(int[][] isConnected, boolean[] visited, int length, int i) {
        for (int j = 0; j < length; j++) {
            //如果城市是相连的，且没有访问过，进去
            if (isConnected[i][j] == 1 && !visited[j]) {
                //访问
                visited[j] = true;
                //再找城市的其他相联城市
                dfs(isConnected, visited, length, j);
            }
        }
    }


    public int bfs(int[][] isConnected) {
        //城市数量
        int length = isConnected.length;
        //省份数量
        int provinces = 0;
        //城市是否被访问过
        boolean isVisited[] = new boolean[length];

        //遍历各个城市
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < length; i++) {
            if (!isVisited[i]) {
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int j = queue.poll();
                    isVisited[j] = true;
                    for (int k = 0; k < length; k++) {
                        if (isConnected[j][k] == 1 && !isVisited[k]) {
                            queue.offer(k);
                        }
                    }
                }
                provinces++;
            }
        }

        return provinces;

    }

    static int mergeFind(int[][] isConnected) {
        int provinces = isConnected.length;
        int[] head = new int[provinces];
        int[] level = new int[provinces];
        for (int i = 0; i < provinces; i++) {
            head[i] = i;
            level[i] = 1;

        }
        for (int i = 0; i < provinces; i++) {
            for (int j = i + 1; j < provinces; j++) {
                if (isConnected[i][j] == 1) {
                    merge(i, j, head, level);
                }
            }
        }
        int count = 0;
//找出所有的head
        for (int i = 0; i < provinces; i++) {
            if (head[i] == i) {
                count++;
            }
        }
        return count;
    }

    //查找head节点
    static int find(int x, int[] arr) {
        if (arr[x] == x)
            return x;
        else
            arr[x] = find(arr[x], arr);//路径压缩，每一个节点直接能找到head
        return arr[x];
    }

    static void merge(int x, int y, int[] arr, int[] level) {
        int i = find(x, arr);
        int j = find(y, arr);
        //深度比较短的树的head往深度大的树上挂，使合并后的深度尽量小if(i == j){
        if (i == j) {
            return;
        }
        if (level[i] <= level[j]) {
            arr[i] = j;
        } else {
            arr[j] = i;
        }
        //深度加1 level[j]++;
        level[j]++;
    }
}
